package algorithms

import (
	"math"
)

//安排活动，必须是一个结束另一个才能开始，看最多能容纳多少活动
//采用贪心算法，每次选择最早结束的活动，判断一下是否和前一个活动兼容即可
func recursiveActiveSelector(s, f []int, res *[]int, k int) {
	m := k + 1
	for k < len(s) && s[k] < f[m] {
		k++
	}
	if k < len(s) {
		*res = append(*res, k)
		recursiveActiveSelector(s, f, res, k)
	} else {
		return
	}
}

func FindMaxCompatibleArray() []int {
	s := []int{1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}
	f := []int{5, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16}
	var res = []int{0}
	recursiveActiveSelector(s, f, &res, 0)
	return res
}

//334. 递增的三元子序列,贪心算法，前两个数尽量小
func increasingTriplet(nums []int) bool {
	if len(nums)<3{
		return false
	}
	a,b:=math.MaxInt8,math.MaxInt8
	for i:=range nums{
		if nums[i]>b {
			return true
		}else if nums[i]>a{
			b=nums[i]
		}else {
			a=nums[i]
		}
	}
	return false
}

//1414. 和为 K 的最少斐波那契数字数目
func findMinFibonacciNumbers(k int) int {
	fibNums:=make([]int,0)
	fibNums=append(fibNums, 1)
	fibNums=append(fibNums, 1)
	for fibNums[len(fibNums)-1]<=k{
		fibNums=append(fibNums, fibNums[len(fibNums)-1]+fibNums[len(fibNums)-2])
	}
	res:=0
	j:=len(fibNums)-1
	for k>0&&j>=0{
		if fibNums[j]<=k{
			k-=fibNums[j]
			res++
		}else {
			j--
		}
	}
	return res
}

//1405. 最长快乐字符串
func longestDiverseString(a int, b int, c int) string {
	f := func(a, b, c int) int {
		if a > b {
			if a > c {
				return a
			}
			return c
		}
		if b > c {
			return b
		}
		return c
	}
	res := ""
	loop: for a > 0 || b > 0 || c > 0 {
		max := f(a, b, c)
		switch max {
		case a:
			if len(res) > 1 && res[len(res)-2:] == "aa" {
				if b!=0||c!=0{
					if b>c{
						res+="b"
						b--
					}else {
						res+="c"
						c--
					}
					break
				}else {
					break loop
				}
			}
			res += "a"
			a--
		case b:
			if len(res) > 1 && res[len(res)-2:] == "bb" {
				if a!=0||c!=0{
					if c>a{
						res+="c"
						c--
					}else {
						res+="a"
						a--
					}
					break
				}else {
					break loop
				}
			}
			res += "b"
			b--
		case c:
			if len(res) > 1 && res[len(res)-2:] == "cc" {
				if b!=0||a!=0{
					if b>a{
						res+="b"
						b--
					}else {
						res+="a"
						a--
					}
					break
				}else {
					break loop
				}
			}
			res += "c"
			c--
		}
	}
	return res
}

//121. 买卖股票的最佳时机
func maxProfit(prices []int) int {
	min:=math.MaxInt32
	ans:=math.MinInt32
	for i:=range prices{
		if prices[i]<min{
			min=prices[i]
		}
		if ans<prices[i]-min{
			ans=prices[i]-min
		}
	}
	return ans
}
